package com.shm.leetcode;

/**
 * 162. 寻找峰值
 * 峰值元素是指其值大于左右相邻值的元素。
 *
 * 给你一个输入数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
 *
 * 你可以假设 nums[-1] = nums[n] = -∞ 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [1,2,3,1]
 * 输出：2
 * 解释：3 是峰值元素，你的函数应该返回其索引 2。
 * 示例 2：
 *
 * 输入：nums = [1,2,1,3,5,6,4]
 * 输出：1 或 5
 * 解释：你的函数可以返回索引 1，其峰值元素为 2；
 *      或者返回索引 5， 其峰值元素为 6。
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 1000
 * -231 <= nums[i] <= 231 - 1
 * 对于所有有效的 i 都有 nums[i] != nums[i + 1]
 *
 *
 * 进阶：你可以实现时间复杂度为 O(logN) 的解决方案吗？
 * @author SHM
 */
public class FindPeakElement {
    public int findPeakElement(int[] nums) {
        if(nums==null){
            return -1;
        }
        if(nums.length==1){
            return 0;
        }
        for(int i=0;i<nums.length;i++){
            if(i==0&&nums[i+1]<nums[i]){
                return i;
            }
            if(i==nums.length-1&&nums[i]>nums[i-1]){
                return i;
            }
            if(i>0&&i<nums.length-1&&nums[i]>nums[i-1]&&nums[i]>nums[i+1]){
                return i;
            }
        }
        return -1;
    }

    /**
     * 对于所有有效的 i 都有 nums[i] != nums[i + 1]
     * @param nums
     * @return
     */
    public int findPeakElement_2(int[] nums) {
        if (nums == null) {
            return -1;
        }
        for (int i = 0; i < nums.length-1; i++) {
            if (nums[i]>nums[i+1]){
                return i;
            }
        }
        return nums.length-1;
    }

    /**
     * 方法二：递归二分查找
     * 算法
     *
     * 我们可以将 numsnums 数组中的任何给定序列视为交替的升序和降序序列。通过利用这一点，以及“可以返回任何一个峰作为结果”的要求，我们可以利用二分查找来找到所需的峰值元素。
     *
     * 在简单的二分查找中，我们处理的是一个有序数列，并通过在每一步减少搜索空间来找到所需要的数字。在本例中，我们对二分查找进行一点修改。首先从数组 numsnums 中找到中间的元素 midmid。若该元素恰好位于降序序列或者一个局部下降坡度中（通过将 nums[i]nums[i] 与右侧比较判断)，则说明峰值会在本元素的左边。于是，我们将搜索空间缩小为 midmid 的左边(包括其本身)，并在左侧子数组上重复上述过程。
     *
     * 若该元素恰好位于升序序列或者一个局部上升坡度中（通过将 nums[i]nums[i] 与右侧比较判断)，则说明峰值会在本元素的右边。于是，我们将搜索空间缩小为 midmid 的右边，并在右侧子数组上重复上述过程。
     *
     * 就这样，我们不断地缩小搜索空间，直到搜索空间中只有一个元素，该元素即为峰值元素。
     *
     * 为了理解本方法的原理，让我们再次讨论前文提到的全部三种情况。
     *
     * 情况 1. 这种情况下，首先找到中间元素 33。由于它处于下降坡度，将搜索空间缩小到 [1, 2, 3]。对于此子数组，22 为中间元素，也处于下降坡度中，于是将搜索空间缩小到 [1, 2]。现在 11 是中间元素并同样处于下降坡度，于是将搜索空间缩小到 [1]。 最终 11 作为答案被正确返回。
     *
     *
     * 1 / 7
     *
     * 情况 2. 这种情况下，首先找到中间元素 33。由于它处于上升坡度，将搜索空间缩小到 [4, 5]。对于此子数组，44 为中间元素，也处于上升坡度中，于是将搜索空间缩小到 [5]。 最终 55 作为答案被正确返回。
     *
     *
     * 1 / 6
     *
     * 情况 3. 这种情况下， 峰值位于中间某处。第一个中间元素是 44。它位于上升坡度，表明峰值在其右侧。于是，搜索空间缩小为 [5, 1]。 现在，55 位于下降坡度（相对其右侧相邻元素）, 搜索空间下降为 [5]。于是，55 被正确识别。
     *
     * 复杂度分析
     *
     * 时间复杂度 : O\big(log_2(n)\big)O(log
     * 2
     * ​
     *  (n))。每一步都将搜索空间减半。因此，总的搜索空间只需要 log_2(n)log
     * 2
     * ​
     *  (n) 步。其中 nn 为 numsnums 数组的长度。
     * 空间复杂度: O\big(log_2(n)\big)O(log
     * 2
     * ​
     *  (n))。每一步都将搜索空间减半。因此，总的搜索空间只需要 log_2(n)log
     * 2
     * ​
     *  (n) 步。于是，递归树的深度为 log_2(n)log
     * 2
     * ​
     *  (n)。
     *
     * 作者：LeetCode
     * 链接：https://leetcode-cn.com/problems/find-peak-element/solution/xun-zhao-feng-zhi-by-leetcode/
     * @param nums
     * @return
     */
    public int findPeakElement_3(int[] nums) {
        if (nums == null) {
            return -1;
        }
        return search(nums,0,nums.length-1);
    }

    int search(int[] nums,int left,int right){
        if(left==right){
            return left;
        }
        int mid = left+(right-left)/2;
        if(nums[mid]>nums[mid+1]){
            return search(nums,left,mid);
        }
        return search(nums,mid+1,right);
    }

    /**
     * 方法三：迭代二分查找
     * 算法
     *
     * 上述二分查找方法使用了递归。我们可以通过迭代达到同样的效果。本方法即为迭代实现二分查找。
     * 复杂度分析
     *
     * 时间复杂度 : O\big(log_2(n)\big)O(log
     * 2
     * ​
     *  (n))。 每一步都将搜索空间减半。因此，总的搜索空间只需要 log_2(n)log
     * 2
     * ​
     *  (n) 步。其中 nn 为 numsnums 数组的长度。
     * 空间复杂度 : O(1)O(1)。 只使用了常数空间。
     *
     * 作者：LeetCode
     * 链接：https://leetcode-cn.com/problems/find-peak-element/solution/xun-zhao-feng-zhi-by-leetcode/
     * @param nums
     * @return
     */
    public int findPeakElement_4(int[] nums) {
        int i=0,j=nums.length-1;
        while (i<j){
            int mid = i+(j-i)/2;
            if (nums[mid]>nums[mid+1]){
                j=mid;
            }else {
                i=mid+1;
            }
        }
        return i;
    }
}
